package ai.zixing.mashibing.basic_class.class06;

public class Code05_FindFirstIntersectNode {

    public static Node getIntersectNode(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node loop1 = getLoopNode(head1);
        Node loop2 = getLoopNode(head2);
        // 两个无环链表相交问题
        if (loop1 == null && loop2 == null) {
            return noLoop(head1, head2);
        }
        // 两个有环链表相交问题
        if (loop1 != null && loop2 != null) {
            return bothLoop(head1, loop1, head2, loop2);
        }
        // 一个有环，一个无环不可能相交
        return null;
    }

    // 找到第入环节点，无环则返回空
    public static Node getLoopNode(Node head) {
        // 不可能出现环
        if (head == null || head.next == null || head.next.next == null) {
            return null ;
        }
        // 第一次相遇在环内
        // 快慢指针在边界条件中判断
        Node slow = head.next;
        Node fast = head.next.next;
        while (slow != fast) {
            if (fast.next == null || fast.next.next == null) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        // 以相同的速度第二次相遇则是入环节点
        fast = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

    // 两个无环链表，返回第一个相交节点，不相交则返回 bull
    public static Node noLoop(Node head1, Node head2) {
        if (head1 == null || head2 == null) {
            return null;
        }
        Node cur1 = head1;
        Node cur2 = head2;
        int size = 0;
        while (cur1 != null) {
            size++;
            cur1 = cur1.next;
        }

        while (cur2 != null) {
            size--;
            cur2 = cur2.next;
        }
        // 当两个链表的尾结点都不相同时，不会相交
        if (cur1 != cur2) {
            return null;
        }
        // cur1 指向长链表
        cur1 = size > 0 ? head1 : head2;
        // cur2 指向端链表
        cur2 = cur1 == head1 ? head2 : head1;

        // 长链表先走 size 个，剩余的节点数 cur1 和 cur2 节点数相等
        size = Math.abs(size);
        while (size != 0) {
            size--;
            cur1 = cur1.next;
        }
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    // 两个链表都有环，相交返回第一个相交节点
    public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
        Node cur1 = null;
        Node cur2 = null;
        // 交点在环外或在入环节点相交
        if (loop1 == loop2) {
            cur1 = head1;
            cur2 = head2;
            return noLoop(cur1, cur2);
        } else {
            // 交点在环内
            cur1 = loop1.next;
            while (cur1 != loop1) {
                if (cur1 == loop2) {
                    // loop1 和 loop2 都是第一个交点
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }

    public static void main(String[] args) {
        // 1->2->3->4->5->6->7->null
        Node head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);

        // 0->9->8->6->7->null
        Node head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

        // 1->2->3->4->5->6->7->4...
        head1 = new Node(1);
        head1.next = new Node(2);
        head1.next.next = new Node(3);
        head1.next.next.next = new Node(4);
        head1.next.next.next.next = new Node(5);
        head1.next.next.next.next.next = new Node(6);
        head1.next.next.next.next.next.next = new Node(7);
        head1.next.next.next.next.next.next = head1.next.next.next; // 7->4

        // 0->9->8->2...
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next; // 8->2
        System.out.println(getIntersectNode(head1, head2).value);

        // 0->9->8->6->4->5->6..
        head2 = new Node(0);
        head2.next = new Node(9);
        head2.next.next = new Node(8);
        head2.next.next.next = head1.next.next.next.next.next; // 8->6
        System.out.println(getIntersectNode(head1, head2).value);

    }
}
